package com.yequan.leetcode.array.hanota;

import com.yequan.leetcode.array.ArrayUtil;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * //在经典汉诺塔问题中，有 3 根柱子及 N 个不同大小的穿孔圆盘，盘子可以滑入任意一根柱子。一开始，所有盘子自上而下按升序依次套在第一根柱子上(即每一个盘子只
 * //能放在更大的盘子上面)。移动圆盘时受到以下限制:
 * //(1) 每次只能移动一个盘子;
 * //(2) 盘子只能从柱子顶端滑出移到下一根柱子;
 * //(3) 盘子只能叠在比它大的盘子上。
 * //
 * // 请编写程序，用栈将所有盘子从第一根柱子移到最后一根柱子。
 * //
 * // 你需要原地修改栈。
 * //
 * // 示例1:
 * //
 * //  输入：A = [2, 1, 0], B = [], C = []
 * // 输出：C = [2, 1, 0]
 * //
 * //
 * // 示例2:
 * //
 * //  输入：A = [1, 0], B = [], C = []
 * // 输出：C = [1, 0]
 * //
 * //
 * // 提示:
 * //
 * //
 * // A中盘子的数目不大于14个。
 * //
 * // Related Topics 递归
 *
 * @author : Administrator
 * @date : 2020/3/14
 */
public class Hanota {

    private static int count = 0;

    public static void main(String[] args) {
        List<Integer> a = new ArrayList<>();
        a.add(0, 2);
        a.add(1, 1);
        a.add(2, 0);
        List<Integer> b = new ArrayList<>();
        List<Integer> c = new ArrayList<>();
        Hanota hanota = new Hanota();
        hanota.hanota(a, b, c);
        ArrayUtil.printList(c);
        System.out.println("交换次数: " + count);
    }

    /**
     * 问题分析:
     * 三根柱子A,B,C,假设A为原始柱子放满了n个盘子,C是目标柱子,B为临时柱子
     * 当n=1时,即A中[1] 则 C->[1]
     * 当n=2时,即A中[2,1] 先将A中的 1 放入 B->[1],再将A中的 2 放入C中 C->[2],最后将B中的 1 放入 C->[2,1]
     * 当n=3时,即A中[3,2,1] 先将A的 2,1 借助C放入 B->[2,1],再将A中3,放入 C->[3],再将B中的 [2,1]借助 A 放入 C->[3,2,1]
     * 当n=n时,即A中[n,n-1,...,1]先将A中的 n-1,...,1 借助C放入 B->[n-1,...1],再将A中的 n 放入 C->[n],最后将B中 n-1,...,1 借助A放入 C->[n,n-1,...,1]
     *
     * @param a
     * @param b
     * @param c
     */
    public void hanota(List<Integer> a, List<Integer> b, List<Integer> c) {
        hanota(a.size(), a, b, c);
    }

    public void hanota(int n, List<Integer> a, List<Integer> b, List<Integer> c) {
        if (n == 1) {
            move(a, c);
            return;
        }
        //借助c,将n-1个数放入b中
        hanota(n - 1, a, c, b);
        //a中n放入c中
        move(a, c);
        //将b中n-1个数借助a放入c中
        hanota(n - 1, b, a, c);
    }

    private void move(List<Integer> list1, List<Integer> list2) {
        list2.add(list1.remove(list1.size() - 1));
    }

}
